package com.atguigu.tree;

import java.util.Arrays;
/*
* 哈夫曼树
* 1.首先对数组进行从大到小排序，每一个数据都是一个节点，每一个节点都额可以看作是一个最简单的二叉树
* 2.取出根节点权值最小的两个二叉树
* 3.组成一个新的二叉树，该新的二叉树的根节点是前面两颗二叉树的根节点权值的和
* 4.再将这一课新的二叉树，以根节点的权值大小进行排序，不断重复2-4，直到数列的数据都被处理结束
*
*
*
* */
/**
 * @author RuiKnag
 * @create 2021-05-18-16:38
 */
public class HeapSort {


    public static void main(String[] args) {
        int[] arr={4,6,8,5,9,-1,98,-345,998};
        heapSort(arr);
        String s = Arrays.toString(arr);
        System.out.println("s = " + s);
    }
    public static void heapSort(int[] arr){
        System.out.println("堆排序");
        //将无序序列构建成一个大顶堆
        for (int i = arr.length/2-1; i >=0 ; i--) {
            adkustHeap(arr,i,arr.length);
        }

        //将大顶堆的输出
        /*
        * 将堆与末尾元素交换顶元素，将最大的元素与末尾进行交换到数组末端
        * 重新调整结构，使其满足堆的定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整和交换步骤，直到整个序列有序
        * */
        int temp=0;
        for(int j=arr.length-1;j>0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adkustHeap(arr,0,j);
        }
    }
    //将一个数组调整成为大顶堆
    /*
    完成对非叶子节点i调整为大顶堆
    * arr待调整数组
    * i表示非叶子节点在数组的调整
    * length 表示对多少个元素继续调整，length逐渐减少
    * */
    public  static void adkustHeap(int[] arr,int i,int length){
        int temp=arr[i];
        for (int j = 2*i+1; j <length ; j=2*j+1) {
            if(j+1<length&&arr[j]<arr[j+1]){
                j++;
            }
            if(temp<arr[j]){
                arr[i]=arr[j];
                i=j;
            }else{
                break;
            }
            arr[i]=temp;
        }
    }
}
